import com.sun.glass.ui.Size;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 * @Author Zhouchb
 * @Create 2022-02-2022/2/26 :14:35
 * @Description
 */
public class 斐波那切数列 {
    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 9, 0, 1, 88, 1, 2};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        System.out.println(fibonacci(3));
    }

    public static int fibonacci(int a) {
        if (a == 0 || a == 1) {
            return a;
        }
        return fibonacci(a - 1) + fibonacci(a - 2);
    }

    public static void sort(int[] arr) {
        int key;
        for (int i = 0; i < arr.length - 1; i++) {
            key = i;
            for (int j = i; j < arr.length - 1; j++) {
                if (arr[key] > arr[j + 1]) {
//                    swap(arr,j,j+1);
                    key = j + 1;
                }
            }
            if (key != i) {
                swap(arr, key, i);
            }
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /*
     * @Author zhouchb
     * @Param [arr]
     * @return void
     * @Description:  插入排序
     * @Date 15:34 2022/2/26
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; --j) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    /*
     * @Author zhouchb
     * @Param
     * @return
     * @Description:
     * @Date 15:34 2022/2/26
     */
    public static void sort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = partition(arr, l, r);
        sort(arr, l, mid - 1);
        sort(arr, mid + 1, r);
    }

    private static int partition(int[] arr, int l, int r) {
        int temp = arr[l];
        int left = l;
        while (left < r) {
            while (arr[r] >= temp && left < r) {
                r--;
            }
            while (arr[left] <= temp && left < r) {
                left++;
            }
            if (left < r) {
                swap(arr, left, r);
            }
        }
        swap(arr, left, l);
        return left;
    }

}

class heheh {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(-1);
        list.add(-2);
        list.add(3);

        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer num = iterator.next();
            if (num < 0) {
                iterator.remove();
            }
        }
        System.out.println(list);
    }
}

class stack {
    public static void main(String[] args) {
/*        h h1 = new h();
        Thread thread = new Thread(h1);
        thread.start();*/
        int i = 0;
        while (true) {
            System.out.println(i++);
            new Thread(new Runnable() {
                @Override
                public void run() {
                    System.out.println(Thread.currentThread().getName());
                    try {
                        Thread.sleep(10000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }).start();
        }

    }

    public void a() {
        a();
    }
}

class h implements Runnable {

    @Override
    public void run() {
        System.out.println("gggggg");
    }
}

class hhh {
    public static void main(String[] args) {

    }
}

class Solution {
    public static void main(String[] args) {
        String s = "“Welcome you, my friends.”";
        Solution so = new Solution();
        System.out.println(s.indexOf("you"));
        //  so.reverseString(s.toCharArray());

    }

    public void reverseString(char[] s) {
        char a;
        for (int i = 0; i < s.length / 2; i++) {
            a = s[i];
            s[i] = s[s.length - i - 1];
            s[s.length - i - 1] = a;
        }
        System.out.println();
    }
}

class QQ {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 8, 9};
        int l = 0;
        int r = arr.length - 1;
        int num = 4;
        int mid = (l + r) / 2;
        while (l<=r) {

            if (num > arr[mid]) {
//                l = mid + 1;
                l = mid ;
            } else if (num < arr[mid]) {
                r = mid;
//                r = mid - 1;
            }else {
                System.out.println("数为"+mid);
                break;
            }
            mid = (l + r) / 2;
            System.out.println("l:"+l+"==r:"+r+"===="+mid);
        }
        if(l>r){
            System.out.println("找不到啊");
        }

    }
}
class qq2{
    public static void main(String[] args) {
        char c = '2';
    }
}
